package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2022-01-06 10:30
 * @description: Functions of this class is
 * 民间解法（使用单调栈来实现）：
 * class Solution {
 *
 * 为什么要用单调栈呢，因为往右子树遍历的过程，value是越来越大的，一旦出现了value小于栈顶元素value的时候，
 * 就表示要开始进入左子树了
 * （如果不是，就应该继续进入右子树，否则不满足二叉搜索树的定义，不理解的请看下二叉搜索树的定义），但是这个左子树是从哪个节点开始的呢？
 *
 *
 * 下面说说单调递增栈的思路和用法。
 * 翻转先序遍历又是root->right->left的，基于这样的性质和遍历方式，我们知道越往右越大，这样，就可以构造一个单调递增的栈，来记录遍历的元素。
 *
 * 简单来说就是，先进根节点，然后一直进入右节点，直到出现左节点的时候，把右节点都出栈，剩下的最后一个就是根节点，然后把跟节点赋给root，继续判断，直到判断完毕
 *
 *     public boolean verifyPostorder(int[] postorder) {
 *         // 单调栈使用，单调递增的单调栈
 *         Stack<Integer> stack = new Stack<>();
 *         int pervElem = Integer.MAX_VALUE;
 *         // 逆向遍历，就是翻转的先序遍历
 *         for (int i = postorder.length - 1;i>=0;i--){
 *             // 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
 *             if (postorder[i] > pervElem){
 *                 return false;
 *             }
 *             while (!stack.isEmpty() && postorder[i] < stack.peek()){
 *                 // 数组元素小于单调栈的元素了，表示到了左子树走了，记录下最后栈中最后一个右子树节点即为根
 *                 // 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
 *                 pervElem = stack.pop();
 *             }
 *             // 这个新元素入栈
 *             stack.push(postorder[i]);
 *         }
 *         return true;
 *     }
 * }
 **/
public class NoNo判断是否二叉搜索树的后序遍历序列 {
    public static void main(String[] args) {

    }
}